package com.zk.algorithm.tree;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.bean.TreeNode;
import com.zk.algorithm.factory.TreeFactory;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zk
 */
@LeetCodeExplore
@Easy
public class ValidateBinarySearchTree {

    // =====================
    // 中序遍历的方式
    // =====================

    public boolean isValidBST(TreeNode root) {
        List<Integer> inOrderList = new ArrayList<>();
        inOrderTraversal(inOrderList, root);

        for (int i = 1; i < inOrderList.size(); i++) {
            if (inOrderList.get(i) <= inOrderList.get(i - 1)) {
                return false;
            }
        }

        return true;
    }

    private void inOrderTraversal(List<Integer> list, TreeNode root) {
        if (root != null) {
            inOrderTraversal(list, root.left);
            list.add(root.val);
            inOrderTraversal(list, root.right);
        }
    }

    // ==================
    // 网友答案
    // ==================

    //
    // 小  <  [左] < 中 < [右] <  大
    //
    //  小  <  中   <  大
    // null < [10] < null
    //      小  <  左  < 中
    //     null < [5] < 10
    //      中  <  右  < 大
    //     10 < [15] < null
    //         10 < [6] < 15
    //         15 < [20] < null
    public boolean isValidBST2(TreeNode root) {
        return helper(null, root, null);
    }

    boolean helper(Integer min, TreeNode root, Integer max) {
        if (root == null)
            return true;

        if ((min != null && root.val <= min) || (max != null && root.val >= max))
            return false;

        return helper(min, root.left, root.val) && helper(root.val, root.right, max);
    }

    // 通不过测试:
    //   10
    //  / \
    // 5  15
    //   / \
    //  6  20
    public boolean isValidBSTWrong(TreeNode root) {
        if (root == null) {
            return true;
        }

        boolean left = root.left != null ? root.val > root.left.val: true;
        boolean right = root.right != null ? root.val < root.right.val : true;
        return left && right && isValidBSTWrong(root.left) && isValidBSTWrong(root.right);
    }

    public static void main(String...args) {
        ValidateBinarySearchTree validateBinarySearchTree = new ValidateBinarySearchTree();

        System.out.println(validateBinarySearchTree.isValidBST2(TreeFactory.buildTree(new int[]{2,1,3})));
        System.out.println(validateBinarySearchTree.isValidBST2(TreeFactory.buildTree(new int[]{10,5,15,Integer.MIN_VALUE, Integer.MIN_VALUE, 6, 20})));
    }

}
